package 前缀系列;
/*
 *前缀树: ： 独立 的 知识 解决  前缀 相关的知识
 *前缀树 是一个  结构 ： 两种实现 方法 ： 
 */
public class aheadTree {
	public static void main(String[]args) {
		TrieTree t=new TrieTree();
		t.add("abcdef");
		t.add("abchanjunhaoef");
		t.add("abczhangef");
		t.add("abchhff");
		t.add("bcdef");
		t.add("cdef");
		System.out.println(t.preStringSum("abc"));
		System.out.println(t.delete("abcdef"));
		System.out.println(t.search("abcdef"));
	}
	static class Node1{
		int pass;
		int end;
		Node1 nexts[];
		public Node1(){
			pass=0;
			end=0;
			nexts=new Node1[26]; //a ~ z 的字符串  这也是 一种局限性的体现 吧  只能 这么多字符 
			// 所以 后面 再 写 一个 HashMap  版本的 方法 一样 只是  path的结构不一样
		}
	}
	//  前缀树  ： 一种 数据 结构  这种结构基本 的功能 创建过程  假设 都是小写的  英文字母
	static class TrieTree {
		private Node1 root;
		public TrieTree() {
			root =new Node1();
		}
		public void add(String s) {
			if(s==null) {
				return ;
			}
			//  这种 操作 就不解释 了吧  用个变量 记录一下   树头 或者链表的 头head 
			Node1 temp=root;// 记录着 总共 有多少个 字符串 加 进来  好像有点多余
			temp.pass++;
			char str [] =s.toCharArray();
			int index =0;
			for(int i=0; i< str.length;i++) {
				index=str[i]-'a';
				if(temp.nexts[index]==null) {
					temp.nexts[index]= new Node1();
				}
				temp=temp.nexts[index];
				temp.pass++;
			}
			temp.end++;
		}
		//  找到  以 某个字符串 为 前缀的 个数
		public int preStringSum(String s) {
			// || search(s)==0 这是 错的  因为 可能 就找不到  s 只是 以s 为前缀而已 前缀树 中 可能并没有 s
			if(s==null ) {
				return 0;
			}
			Node1 temp=root;
			char str [] =s.toCharArray();
			int index =0;
			for(int i=0;i < str.length;i++) {
				index= str[i]- 'a';
				if(temp.nexts[index]==null) {
					return 0;
				}
				temp=temp.nexts[index];
			}
			 return temp.pass;
		}
		public boolean delete(String s) {
			if(s==null || search(s)==0) {
				return false;
			}
			Node1 temp= root;
			temp.pass--;
			int index=0;
			char []str= s.toCharArray();
			for(int i=0;i< str.length;i++) {
				index=str[i]-'a';
				//  已经通过 search 查到 search 的存在  还判断 个屁的  
				if(--temp.nexts[index].pass == 0) {
					temp.nexts[index]=null;
					return true;
				}
				temp=temp.nexts[index];
//				if(temp.nexts[index] !=null) {
//					Node1 t = temp.nexts[index].nexts[str[i+1]-'a'];
//					if(t!=null  && t.pass==0) {
//						temp.nexts[index].nexts[str[i+1]-'a']=null;
//				}
//					temp=temp.nexts[index];
//					temp.pass--;
//				}
				temp.end--;
			}
			return true;
		}
		public int search(String s) {
			if(s==null) {
				return 0;
			}
			Node1 temp= root;
			int index=0;
			char []str= s.toCharArray();
			for(int i=0;i< str.length;i++) {
				index=str[i]-'a';
				if(temp.nexts[index]==null) {
					return 0;
				}
				temp=temp.nexts[index];
			}
			return temp.end;
		}
	}
}
